package com.julius.design.suanfa.dynamic;


/**
 * @author julius
 * @date 2021-11-01 上午 9:55
 * <p>
 *      翻译数字
 *      给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。
 *      一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
 *
 *      https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
 * </p>
 */
public class TranslateNumber {

    /**
     * 转换数字  其实就是数字有多少种拆解形式
     *  多少种解、方案、步骤这种直接找递推公式！！！！！
     * 12345
     * bcdefg   bxfg  mdefg
     *
     * 动态规划：
     *      状态定义：
     *          dp[i] 代表以第i位数字结尾时的翻译方案个数
     *          dp[i-1] 代表以第i-1位数字结尾时的翻译方案个数
     *      状态转移方程：
     *          当第i位数字和第i-1位数字结合位于[10,25]时。可以联合翻译。此时有dp[i-2]种方案，否则有dp[i-1]种方案
     *          dp[i] = dp[i-1]+dp[i-2]
     *      初始值：
     *          dp[0] = dp[1] = 0
     *      返回值：
     *          dp[i]
     *
     *  12258（5）
     *
     *  1 2 2 5 8
     *
     *  1 2 25 8
     *
     *  1 22 5 8
     *
     *  12 2 5 8
     *
     *  12 25 8
     *
     *
     * @param num
     * @return
     */
    public static int translateNum(int num){

        //dp数组的初始化 a(dp[i-1]) b(dp[i-2])
        int a = 1,b = 1;

        //数字上的指针对应的值和指针的后一位对应的值 x当前指针，y指针的后一位
        int x,y = num %10;
        //拆解数字的各个位置的数字
        while (num > 0){
            //指针前移一位
            num = num / 10;
            x = num % 10;

            int temp = 10*x+y;
            int c;
            if((temp >= 10) && (temp <= 25)){
                c = a + b;
            }else{
                c = a;
            }
            //dp数组指针前移一位
            b = a;
            a = c;
            //数字指针前移一位
            y = x;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println("翻译方案个数为："+translateNum(12258));
    }
}
